<!DOCTYPE html>
<html lang="en">





<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/apple-touch-icon.png">
  <link rel="icon" type="image/png" href="https://img.fungnotl.cn/basket.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  <meta name="description" content="">
  <meta name="author" content="John Doe">
  <meta name="keywords" content="">
  <title>Java希尔排序详解 ~ fungnotl的博客</title>

  <link rel="stylesheet" href="/lib/font-awesome/css/all.min.css"  >
<link rel="stylesheet" href="/lib/bootstrap/css/bootstrap.min.css"  >
<link rel="stylesheet" href="/lib/mdbootstrap/css/mdb.min.css"  >
<link rel="stylesheet" href="/lib/github-markdown/github-markdown.min.css"  >
<link rel="stylesheet" href="//at.alicdn.com/t/font_1067060_qzomjdt8bmp.css">


  <link rel="stylesheet" href="/lib/prettify/tomorrow-night-eighties.min.css"  >

<link rel="stylesheet" href="/css/main.css"  >


  <link rel="stylesheet" href="/lib/fancybox/jquery.fancybox.min.css"  >


</head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>fungnotl的博客</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          <li class="nav-item">
            <a class="nav-link" href="/">主页</a>
          </li>
        
          
          
          <li class="nav-item">
            <a class="nav-link" href="/archives/">归档</a>
          </li>
        
          
          
          <li class="nav-item">
            <a class="nav-link" href="/tags/">标签</a>
          </li>
        
          
          
          <li class="nav-item">
            <a class="nav-link" href="/about/">我</a>
          </li>
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>


</nav>

    <div class="view intro-2" id="background"
         style="background: url('https://fungnotl-img.oss-cn-hangzhou.aliyuncs.com/index.jpg')no-repeat center center;
           background-size: cover;
           background-attachment: fixed;">
      <div class="full-bg-img">
        <div class="mask rgba-black-light flex-center">
          <div class="container text-center white-text fadeInUp">
            <span class="h2" id="subtitle">
              
            </span>

            
              <br>
              
                <p class="mt-3">
                  <i class="fas fa-calendar-alt" aria-hidden="true"></i>&nbsp;
                  Saturday, October 19th 2019, 4:22 pm
                </p>
              

              <p>
                
                  
                  &nbsp;<i class="far fa-chart-bar"></i>
                  <span class="post-count">
                    1.1k 字
                  </span>&nbsp;
                

                
                  
                  &nbsp;<i class="far fa-clock"></i>
                  <span class="post-count">
                      5 分钟
                  </span>&nbsp;
                

                
                  <!-- 不蒜子统计文章PV -->
                  
                  &nbsp;<i class="far fa-eye" aria-hidden="true"></i>&nbsp;
                  <span id="busuanzi_container_page_pv">
                    <span id="busuanzi_value_page_pv"></span> 次
                  </span>&nbsp;
                
              </p>
            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="py-5 z-depth-3" id="board">
        <div class="post-content mx-auto" id="post">
          <div class="markdown-body">
            <h2 id="希尔排序"><a href="#希尔排序" class="headerlink" title="希尔排序"></a>希尔排序</h2><p>刚接触希尔排序的时候,我是懵的,因为在学校根本没有学过希尔排序啊!</p>
<p>查询资料:希尔排序是插入排序的升级版;</p>
<p>从维基百科截取的Java实现希尔排序的代码</p>
<pre><code class="java">public static void shellSort(int[] arr) {
        int length = arr.length;
        int temp;
        for (int step = length / 2; step &gt;= 1; step /= 2) {
            for (int i = step; i &lt; length; i++) {
                temp = arr[i];
                int j = i - step;
                while (j &gt;= 0 &amp;&amp; arr[j] &gt; temp) {
                    arr[j + step] = arr[j];
                    j -= step;
                }
                arr[j + step] = temp;
            }
        }
    }</code></pre>
<p>我们来简单的试一下:</p>
<pre><code class="java">public class ShellSortFromWiki{
  public static void main(String[] args){
    int[] a = {4, 9, 11, 3, 8, 6, 2, 7, 13, 1, 12, 5, 10};
    shellSort(a);
    print(a);
  }
  public static void shellSort(int[] arr) {
        int length = arr.length;    //获取数组的长度
        int temp;                   //临时变量temp
        // step是每个区域的数值的个数,当每个区域排序到不能再继续往下排的时候;
        // 将区域再次变小,这里是 step /= 2,将每个区域再分一半
        for (int step = length / 2; step &gt;= 1; step /= 2) {
            for (int i = step; i &lt; length; i++) {
                temp = arr[i];
                int j = i - step;
                while (j &gt;= 0 &amp;&amp; arr[j] &gt; temp) {
                    arr[j + step] = arr[j];
                    j -= step;
                }
                arr[j + step] = temp;
            }
        }
    }

    static void print(int[] a){
      for (int i = 0; i &lt; a.length; i++) {
        System.out.print(a[i] + &quot; &quot;);
      }
    }
}</code></pre>
<p>打印:</p>
<p>对以上代码稍加修改,打印出每一次排序的过程</p>
<pre><code class="java">2 9 11 3 8 6 4 7 13 1 12 5 10
2 7 11 3 8 6 4 9 13 1 12 5 10
2 7 11 3 8 6 4 9 13 1 12 5 10
2 7 11 1 8 6 4 9 13 3 12 5 10
2 7 11 1 8 6 4 9 13 3 12 5 10
2 7 11 1 8 5 4 9 13 3 12 6 10
2 7 11 1 8 5 4 9 13 3 12 6 10
1 7 11 2 8 5 4 9 13 3 12 6 10
1 7 11 2 8 5 4 9 13 3 12 6 10
1 7 5 2 8 11 4 9 13 3 12 6 10
1 7 5 2 8 11 4 9 13 3 12 6 10
1 7 5 2 8 11 4 9 13 3 12 6 10
1 7 5 2 8 11 4 9 13 3 12 6 10
1 7 5 2 8 11 3 9 13 4 12 6 10
1 7 5 2 8 11 3 9 13 4 12 6 10
1 7 5 2 8 6 3 9 11 4 12 13 10
1 7 5 2 8 6 3 9 11 4 12 13 10
1 7 5 2 8 6 3 9 11 4 12 13 10
1 5 7 2 8 6 3 9 11 4 12 13 10
1 2 5 7 8 6 3 9 11 4 12 13 10
1 2 5 7 8 6 3 9 11 4 12 13 10
1 2 5 6 7 8 3 9 11 4 12 13 10
1 2 3 5 6 7 8 9 11 4 12 13 10
1 2 3 5 6 7 8 9 11 4 12 13 10
1 2 3 5 6 7 8 9 11 4 12 13 10
1 2 3 4 5 6 7 8 9 11 12 13 10
1 2 3 4 5 6 7 8 9 11 12 13 10
1 2 3 4 5 6 7 8 9 11 12 13 10
1 2 3 4 5 6 7 8 9 10 11 12 13
1 2 3 4 5 6 7 8 9 10 11 12 13</code></pre>
<p>总共30行数据,减去最后一行打印,总共29条;</p>
<h3 id="排序方式"><a href="#排序方式" class="headerlink" title="排序方式:"></a>排序方式:</h3><blockquote>
<p>希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）.</p>
</blockquote>
<blockquote>
<p>注意:如果你看这些文字实在是看不懂,建议拿出纸笔,一步一步算(小编比较愚钝,就是这么做的);</p>
</blockquote>
<blockquote>
<p>这里维基百科提供的代码是根据数组的长度除以2[for (int step = length / 2; step &gt;= 1; step /= 2)];</p>
</blockquote>
<p><strong>但这并不是最佳的解决方法</strong></p>
<p><em>我们来比较一下相同的数组排序次数的差别:</em></p>
<p>插入排序:38次</p>
<p>二分希尔排序:29次</p>
<p>knuth希尔排序:21次</p>
<p>明显是knuth希尔排序更快,下面介绍一下knuth希尔排序算法:</p>
<pre><code class="java">public static void sort(int[] arr) {
        int h = 1;
        while(h &lt;= arr.length /3 ) {
            h = h*3 + 1;
        }

        for(int gap = h; gap &gt; 0; gap = (gap-1)/3) {

            for(int i=gap; i&lt;arr.length; i++) {
                for(int j=i; j&gt;gap-1; j-=gap) {
                    if(arr[j] &lt; arr[j-gap]) {
                        swap(arr, j, j-gap);
                    }
                }
            }
        }
    }</code></pre>
<h2 id="几种常见的Gap序列"><a href="#几种常见的Gap序列" class="headerlink" title="几种常见的Gap序列:"></a>几种常见的Gap序列:</h2><ul>
<li>希尔原本的Gap：N/2、N/4、…1(反复除以2)</li>
<li>Hibbard的Gap：1、3、7、…、2k-1（k表示第几个gap）</li>
<li>Knuth的Gap: 1、4、13、…、(3k -1) / 2（k表示第几个gap） 4）Sedgewick的Gap: 1、5、19、41、109、…</li>
</ul>
<p>看不懂?!</p>
<p><strong>拿出笔来算 !!</strong></p>

            <hr>
          </div>
          <br>
          <div>
            <p>
            
            
              <span>
                <i class="iconfont icon-tag"></i>
                
                  <a class="hover-with-bg" href="/tags/%E6%8E%92%E5%BA%8F">排序</a>
                
              </span>
            
            </p>
            
              <p class="note note-warning">本博客所有文章除特别声明外，均采用 <a href="https://zh.wikipedia.org/wiki/Wikipedia:CC_BY-SA_3.0%E5%8D%8F%E8%AE%AE%E6%96%87%E6%9C%AC" target="_blank" rel="nofollow noopener noopener">CC BY-SA 3.0协议</a> 。转载请注明出处！</p>
            
          </div>
        </div>
      </div>
    </div>
    <div class="d-none d-lg-block col-lg-2 toc-container">
      
  <div id="toc">
    <p class="h4"><i class="far fa-list-alt"></i>&nbsp;TOC</p>
    <div id="tocbot"></div>
  </div>

    </div>
  </div>
</div>

<!-- custom -->


<!-- Comments -->
<div class="col-lg-7 mx-auto nopadding-md">
  <div class="container comments mx-auto" id="comments">
    
      <br><br>
      
      
   <!-- 来必力City版安装代码 -->
<div id="lv-container" data-id="city" data-uid="MTAyMC80Nzg4My8yNDM4MA==">
	<script type="text/javascript">
   (function(d, s) {
       var j, e = d.getElementsByTagName(s)[0];

       if (typeof LivereTower === 'function') { return; }

       j = d.createElement(s);
       j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
       j.async = true;

       e.parentNode.insertBefore(j, e);
   })(document, 'script');
	</script>
<noscript> 为正常使用来必力评论功能请激活JavaScript</noscript>
</div>
<!-- City版安装代码已完成 -->
  
  
    
  </div>
</div>

    
  </main>

  
    <a class="z-depth-1" id="scroll-top-button" href="#" role="button">
      <i class="fa fa-chevron-up scroll-top-arrow" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">Search</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">keyword</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  <footer class="mt-5">
  <div class="text-center py-3">
    <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><b>Hexo</b></a>
    <i class="iconfont icon-love"></i>
    <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener"> <b>Fluid</b></a>
    <br>

    
  
    <!-- 不蒜子统计PV -->
    
    &nbsp;<span id="busuanzi_container_site_pv">总访问量 
          <span id="busuanzi_value_site_pv"></span> 次</span>&nbsp;
  
  
    <!-- 不蒜子统计UV -->
    
    &nbsp;<span id="busuanzi_container_site_uv">总访客数 
            <span id="busuanzi_value_site_uv"></span> 人</span>&nbsp;
  
  <br>



    
  <!-- 备案信息 -->
  <a href="http://beian.miit.gov.cn/" target="_blank"
     rel="nofollow noopener">浙ICP备19040843号</a>
  


  </div>
</footer>

<!-- SCRIPTS -->
<script src="/lib/jquery/jquery.min.js" ></script>
<script src="/lib/popper/popper.min.js" ></script>
<script src="/lib/bootstrap/js/bootstrap.min.js" ></script>
<script src="/lib/mdbootstrap/js/mdb.min.js" ></script>
<script src="/js/main.js" ></script>


  <script src="/js/lazyload.js" ></script>



  
    <script src="/lib/tocbot/tocbot.min.js" ></script>
  
  <script src="/js/post.js" ></script>



  <script src="/lib/smooth-scroll/smooth-scroll.min.js" ></script>



  <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>


<!-- Plugins -->


  

  

  

  

  




  <script src="/lib/prettify/prettify.min.js" ></script>
  <script>
    $(document).ready(function () {
      $('pre').addClass('prettyprint  linenums');
      prettyPrint();
    })
  </script>



  <script src="/lib/typed/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "Java希尔排序详解&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 50,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>



  <script src="/lib/anchor/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "false",
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script src="/js/local-search.js" ></script>
  <script>
    var path = "/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      getSearchFile(path);
      this.onclick = null
    }
  </script>



  <script src="/lib/fancybox/jquery.fancybox.min.js" ></script>
  <script>
    $("#post img:not(.no-zoom img, img[no-zoom])").each(
      function () {
        var element = document.createElement("a");
        $(element).attr("data-fancybox", "images");
        $(element).attr("href", $(this).attr("src"));
        $(this).wrap(element);
      }
    );
  </script>





  





</body>
</html>
